前兩天都在寫前綴和，今天該寫寫差分。

• 前綴和的定義：

  • 對於一個整數陣列 A = [A1, A2, A3, ..., An]，前綴和 S 的公式為： 𝑆[𝑖] = 𝐴[0] + 𝐴[1] + 𝐴[2] + ⋯ + 𝐴[𝑖]。 簡單來說，前綴和 S[i] 是陣列從開頭到第 i 個元素的總和。

• 差分陣列的定義:

  • 對於同樣的整數陣列 A，差分陣列 D 是每個元素與前一個元素的差值： 𝐷[𝑖] = 𝐴[𝑖] − 𝐴[𝑖−1] (𝑖>1)
  • 差分陣列做前綴和，會還原原本的陣列 A

舉例

整數陣列 A:  3  1  2  7
前綴和   S:  3  4  6 13
差分陣列 D:  3 -2  1  5

前綴和 vs. 差分

前綴和（Prefix Sum）：適合用來快速計算某個區間內的總和，通常用於查詢區間和的問題。
差分（Difference Array）：適合在區間內進行加減操作，通常用於批量修改區間內數值的問題。

吳邦一教授在Python-LeetCode 581 第四招 前綴和 Prefix Sum 講解了非常多前綴和的進階題，收穫良多，也建議大家去看看。

1094. Car Pooling (medium)

題目敘述:
車子一路向東行，不回頭，這台車有夠客的上限。
給一個陣列 trips，其中 trips[i] = [numPassengers_i, from_i, to_i] 表示第 i 個行程有 numPassengers_i 名乘客在 from_i 位置上車，並在 to_i 位置下車。
我們需要判斷，車輛在所有行程中能否在任意時刻超過其載客上限。如果可以接送所有行程中的所有乘客，則傳回 true，否則傳回 false

解題思路：
這題非常適合使用 差分陣列來解決，不用為每個行程從 from_i 到 to_i 都去減加乘客數，而是記錄在差分陣列裡，最後再計算前綴和，算出每個公里數車上有的乘客數。

• 在 fromi 位置，上車後，車輛空位減少 numPassengersi。
• 在 toi 位置，乘客下車後，車輛空位增加 numPassengersi。
  透過一個 差分陣列，我們記錄每個位置的空位變化，最終再用 前綴和 的方式累加差分來檢查是否有任何時刻車輛超載（即空位小於 0）。

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff (1001, 0);
        // The available space of the vehicle at the initial position is capacity
        diff[0] = capacity;
        
        for (auto &trip: trips) {
            int numPassengers = trip[0], from = trip[1], to = trip[2];
            diff[from] -= numPassengers;
            diff[to] += numPassengers;
        }
        
        // to record the prefix sum
        int prefixSum = 0;
        
        for (int d: diff) {
            prefixSum += d;
            // If the vacancy is less than 0 at any time, it means overloading
            if (prefixSum < 0) return false;
        }
        return true;
    }
};

時間複雜度：每次操作的時間是 O(n)，其中 n 為行程的數量。